#include "quickSort.h"
#include <algorithm>

void quickSort(vector<int> & arr)
{
	quickSort(arr, 0, arr.size() - 1);
}


void quickSort(vector<int> & arr, int left, int right)
{

	if (right - left + 1 >= 5)
	{
		int pivot = medium(arr, left, right);
		int i = left;
		int j = right - 1;

		for (;;)
		{

			while (arr[++i] < pivot)
				;
			while (arr[--j] > pivot)
				;
			if (i < j)
				swap(arr[i], arr[j]);
			else
				break;
		}
		
		swap(arr[i], arr[right - 1]);
		quickSort(arr, left, i - 1);
		quickSort(arr, i + 1, right);



	}
	else{

		insertionSort(arr, left, right);
	}


}


void insertionSort(vector<int> & arr, int left, int right)
{
	int p, i, temp;

	for (p = left + 1; p <= right; ++p)
	{
		temp = arr[p];
		for (i = p; i > left && arr[i - 1] > temp; --i)
			arr[i] = arr[i - 1];
		arr[i] = temp;


	}

}


int medium(vector<int> & arr, int left, int right)
{

	int center = (left + right) / 2;
	
	if (arr[left] > arr[center])
		swap(arr[left], arr[center]);
	if (arr[left] > arr[right])
		swap(arr[left], arr[right]);
	if (arr[center] > arr[right])
		swap(arr[center], arr[right]);

	swap(arr[center], arr[right - 1]);
	return arr[right - 1];
}